package com.example.javalib.math;

/**
 * @Description:统计素数个数
 * @author: zcs
 * @email: 1059737741@qq.com
 * create at 2022/1/20 9:41
 */

public class PrimeCount {


    public static void main(String[] args) {
        int num = 100 ;
        int k = primeNums(num);
        int i = eratosthense(num);
        System.out.println("素数个数："+k);
        System.out.println("素数个数："+i);

    }
    //方式1 暴力算法
    private static int primeNums(int num){
        int count = 0 ;
        for (int i = 2; i < num ; i++) {
            count +=  isPrime(i) ? 1 : 0 ;
        }
        return  count;
    }

    private static boolean isPrime(int x) {
        //System.out.println("当前数字：" + x);
        for (int i = 2; i * i <= x; i++) {
            if(x % i == 0){
                return  false;
            }
        }
        System.out.println("当前素数数字：" + x);
        return  true;
    }


    // 方式2 埃筛法
    // 素数 ，非素数（合数）
    public static int eratosthense(int num){
        int count = 0 ;
        boolean[] booleans = new boolean [num];//false 是素数

        for (int i = 2; i < num; i++) {
            if(!booleans[i]){
                count++;
                //for (int j = i * 2 ; j < num ; j += i) { // j是 合数的标记位
                for (int j = i * i ; j < num ; j += i) { // j是 合数的标记位
                    booleans[j] = true;
                }
            }

        }
        return  count;
    }

}
